--[[
    优先队列 priority_queue

    1.清空队列
    2.入队
    3.出队
    4.取节点个数
    优先级越大的先插入到队列头，这样优先级大的先出队列

    --用完全二叉树的大小堆实现更好

    node = {
        id 作为大小比较值
    }
--]]

local table_insert = table.insert
local table_remove = table.remove

local PQueue = {}

function PQueue.new(...)
    local instance = setmetatable({}, {__index=PQueue})
    instance:ctor(...)
    return instance
end

function PQueue:ctor()
    self.head = 0 --标记
    self.tail = 1 --标记
    self.data = {} --用于存放数据
    self.count = 0
    self:clear()
end

--队列的方式实现, 每次插入都要遍历列表查找
function PQueue:push(node)
    --大的值放在头
    local index = self.tail
    local cur_node = self.data[index]
    if not cur_node then
        self.tail = self.tail - 1
        self.data[self.tail] = node
        self.count = self.count + 1
        return
    end
    for k=self.head, self.tail, -1 do
        cur_node = self.data[k]
        if cur_node.id < node.id then
            --插入, 别的node往后移
            self.tail = self.tail - 1
            for m=self.tail, k-1 do
                self.data[m] = self.data[m+1]
            end
            self.data[k] = node
            self.count = self.count + 1
            return
        end
    end
    self.tail = self.tail - 1
    self.data[self.tail] = node
    self.count = self.count + 1
    return
end

function PQueue:pop()
    if self.head < self.tail then
        return
    end
    local value = self.data[self.head]
    self.data[self.head] = nil
    self.head = self.head - 1
    self.count = self.count - 1
    return value
end

function PQueue:getData()
    return self.data
end

function PQueue:print()
    for i = self.tail, self.head do
        print(i, self.data[i].id)
    end
end

function PQueue:size()
    return self.count
end

function PQueue:clear()
    self.head = 0 --标记
    self.tail = 1 --标记
    self.data = {} --用于存放数据
    self.count = 0
end

function PQueue:empty()
    return self.count > 0
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "pqueue.lua" then
    local start_time = os.time()
    print("_______", start_time)
    local queue = PQueue.new()
    for i=1, 10000 do
        queue:push({id=math.random(1, 100000)})
    end
    --queue:print()
    print("_______", os.time() - start_time)

    while queue:empty() do
        queue:pop()
    end
    --local a = queue:pop()
    --local b = queue:pop()
    --print("pop:", a.id, b.id)
    --queue:print()
    print("_______", os.time() - start_time)

end

return PQueue